package com.study.algorithm.basicalsort.imp;

import com.study.algorithm.basicalsort.BasicalSort;
import com.study.algorithm.utils.ListUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 希尔排序(插入排序的改进版，其中方法可以复用）
 * 原理：
 * 就是插入排序的改进版，简单理解为插入排序的排序间距为1
 * 而快速排序是通过特定间距组合，实现减少数据移动的改进版插入排序
 */
public class ShellSortImpl implements BasicalSort {


    @Override
    public List<Integer> basicalSort(List<Integer> originList) {
        int size = originList.size();
        List<Integer> destList = ListUtil.DeepClone(originList);
        if (size <= 1) {
            return destList;
        }
        List<Integer> gaps = generateGapsElement(size);
        for (int gap : gaps) {
            for (int group = 0; group < gap; group++) {
                insertSort(destList, group, gap);
            }
        }
        return destList;
    }

    /**
     * 就是普通的插入排序，不过是将间距为一，改为使用特定间距gap进行插入排序
     *
     * @param destList   目标集合（排序后的集合）
     * @param startIndex 开始索引
     * @param gap        间距
     */
    private void insertSort(List<Integer> destList, int startIndex, int gap) {
        int size = destList.size();
        for (int currIndex = startIndex; currIndex < size; currIndex += gap) {
            insertIntoOrderList(destList, startIndex, currIndex, gap);
        }
    }


    private void insertIntoOrderList(List<Integer> list, int startIndex, int currIndex, int gap) {
        int inserVal = list.get(currIndex);
        int endInsertIndex = currIndex - gap;//将当前值插入到前n-1个有序值中
        int insertIndex = findInsertIndex(list, startIndex, endInsertIndex, inserVal, gap);
        if (insertIndex == currIndex) {
            return;
        }
        rightMoveForGapPosition(list, insertIndex, endInsertIndex, gap);
        list.set(insertIndex, inserVal);
    }

    private int findInsertIndex(List<Integer> list, int startIndex, int endIndex, int inserVal, int gap) {
        int insertIndex = endIndex + gap;//代表无需插入，改值即为最大值
        for (int currIndex = startIndex; currIndex <= endIndex; currIndex += gap) {
            int currVal = list.get(currIndex);
            if (inserVal < currVal) {
                insertIndex = currIndex;
                break;
            }

        }
        return insertIndex;
    }

    private void rightMoveForGapPosition(List<Integer> list, int startMoveIndex, int endMoveIndex, int gap) {
        int size = list.size();
        if (startMoveIndex > endMoveIndex || endMoveIndex + gap + 1 > size) {
            throw new ArrayIndexOutOfBoundsException("数组越界");
        }
        int preVal = list.get(startMoveIndex);
        for (int currIndex = startMoveIndex + gap; currIndex <= endMoveIndex + gap; currIndex += gap) {
            int currVal = list.get(currIndex);
            list.set(currIndex, preVal);
            preVal = currVal;
        }
    }


    private List<Integer> generateGapsElement(int totalSize) {
        List<Integer> gaps = new ArrayList<>();
        int gapElement = getNextMiddleOddNum(totalSize);
        for (; gapElement > 1; gapElement = getNextMiddleOddNum(gapElement)) {
            gaps.add(gapElement);
        }
        gaps.add(1);
        return gaps;
    }

    /**
     * 得到下一个中位点的奇数
     * 不同的策略直接影响效率，这只是一个例子
     *
     * @param num
     * @return
     */
    private int getNextMiddleOddNum(int num) {
        int nextPrimeNum = num / 2;
        boolean isNotOdd = (nextPrimeNum / 2) * 2 == nextPrimeNum;
        return nextPrimeNum != 1 && isNotOdd ?
                nextPrimeNum + 1 : nextPrimeNum;
    }

}
